1. Field of the Invention
The present invention relates to a communication network such as an ad hoc network comprising a plurality of communication terminals, to the terminals in the network, and in particular to the routing method employed in the network.
2. Description of the Related Art
Communication in an ad hoc network takes place by the routing of packets from a source node or terminal to a destination node or terminal on a path that may lead through one or more intermediate or relay nodes or terminals. (‘Terminal’ will be used below as a synonym for ‘node’.) All of the terminals in the network are capable of operating as routers, that is, of designating the paths or routes that packets will follow. The routing methods employed in an ad hoc network include single-path schemes such as the one described in, for example, ‘Ad hoc On-Demand Distance Vector (AODV) Routing’, available on the Internet as of Oct. 16, 2003 at the URL shown in FIG. 41A, and multipath schemes such as the one described in, for example, ‘On-demand Multipath Distance Vector Routing in Ad Hoc Networks’, available on the Internet as of Oct. 16, 2003 at the URL shown in FIG. 41B.
Single-path routing schemes are unstable because communication can be broken off if even a single terminal is disabled or moved to another location. Multipath schemes are more stable because if communication breaks down on one path it can be continued without interruption on another path.
Conventional multipath routing schemes, however, invite a further problem. As numerous paths crisscross the network between a source terminal and a destination terminal, neighboring terminals tend to start transmitting packets at identical times, causing the packet signals to interfere or collide. Such interference leads to packet loss and communication delays. This problem becomes especially pronounced when all terminals route packets through a single terminal or a single set of terminals between the source terminal and the destination terminal.
Another problem with conventional multipath schemes is their squandering of network resources when communication conditions are stable.